package 代码随想录_单调栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author zx
 * @create 2023-02-07 22:31
 */
public class 每日温度_739 {
    /**
     * 精简版
     * @return 看第二个题解的动画演示图,具体思路参考代码随想录
     * 以后做单调栈题自己规定：顺序为从栈头到栈底的顺序，(栈内将要存放的数据的顺序为规定方向递增)所以本题是单调递增栈
     */
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            /**
             * 取出下标进行元素值的比较
             */
            while (!stack.isEmpty() &&
                    temperatures[i] > temperatures[stack.peek()]) {
                int preIndex = stack.pop();
                res[preIndex] = i - preIndex;
            }
            stack.push(i);
        }
        return res;
    }
    /**
     * 详尽版
     * 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
     * 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
     * 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
     */
    public int[] dailyTemperatures2(int[] temperatures) {
        // 递减栈
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[temperatures.length];
        for (int i = 1; i < temperatures.length; i++) {
            if (temperatures[i] < temperatures[stack.peek()]) {                       // 情况一
                stack.push(i);
            } else if (temperatures[i] == temperatures[stack.peek()]) {               // 情况二
                stack.push(i);
            } else {
                while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { // 情况三
                    res[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }
        return res;
    }
}
